%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsection{Übungsblatt 2, 24.10.}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (i) - \buchmann{4.16.20}}

\begin{itemize}
\item Injektiv affine lineare Funktion: $f(v) = \mathbf{A}v+\mathbf{b}$ mit $\mathbf{A}$ invertierbar
\vspace*{5mm}
\item[$\Rightarrow$] Injektiv affine lineare Funktion (Beispiel): $f(v) = f^{-1}(v) = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0& 1 \end{pmatrix}v+\begin{pmatrix} 1\\1\\1\end{pmatrix}$
\vspace*{5mm}
\item[$\Rightarrow$] Wertetabelle (Beispiel):
\begin{tabular}{c|c}
$v$ & $f(v)$\\
\hline
$(0,0,0)$ & $(1,1,1)$\\
$(0,0,1)$ & $(1,1,0)$\\
$(0,1,0)$ & $(1,0,1)$\\
$\vdots$ & $\vdots$\\
$(1,1,1)$ & $(0,0,0)$\\
\end{tabular}
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (ii) - \buchmann{4.16.22}}

\begin{itemize}
\item Tabelle Klartexte und Chiffrat
\begin{tabular}{l|c|c|c}
Alphabet A...Z & R & O & T \\
Alphabet 1...26 & 17 & 14 & 19 \\
\hline
Alphabet 1...26 & 6 & 20 & 19 \\
Alphabet A...Z & G & U & T \\
\end{tabular}\\
\vspace*{5mm}
\item lineare Funktion gewählt: $f(v) = \begin{pmatrix} x & 0 & 0\\ 0 & y & 0 \\ 0 & 0& z \end{pmatrix}v+\begin{pmatrix} 0\\0\\0\end{pmatrix}$\\
\vspace*{5mm}
\item es ergibt sich somit ein lineares Gleichungssystem: 
\begin{align*}
17x &\equiv 6 \mod 26\\
14y &\equiv 20 \mod 26\\
19z &\equiv 19 \mod 26
\end{align*}
\begin{align*}
17x &\equiv 6 \mod 26\\
17*23x &\equiv 20*23 \mod 26 \\
x &\equiv 8 \mod 26
\end{align*}
\begin{align*}
14y &\equiv 20 \mod 26\\
7y &\equiv 10 \mod 13\\
7*2y &\equiv 10*2 \mod 13\\
y &\equiv 7 \mod 13\\
(y &\equiv 20 \mod 13)
\end{align*}\\
\vspace*{0mm}
\item[$\Rightarrow$] Ergebnis
\begin{displaymath}
f(v) = \begin{pmatrix} 8 & 0 & 0\\ 0 & 7 & 0 \\ 0 & 0& 1 \end{pmatrix}v+\begin{pmatrix} 0 \\ 0 \\ 0\end{pmatrix}
\end{displaymath}
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (iii) - \buchmann{6.5.3}}

\begin{itemize}
\item Allgemein: $\overline{b}$ bedeutet bitweise Investierung von $b$
\item DES ist eine Erweiterung der Feistel-Chiffre \\
$\Rightarrow$ Verschlüsselungsfunktion pro Runde effektiv: $E(R)\oplus K$.  
\item Expansionsfunktion $E(R): \{0,1\}^{32}\rightarrow \{0,1\}^{48}$ 
\item 16 Abbildungen doppelt \\ 
$\Rightarrow \overline{E(R)}=E(\overline{R})$.
\item Selbiges gilt für den Rundenschlüssel $K_i$. \\
$\Rightarrow \overline{K_i(k)}=K_i(\overline{k})$.
\item per Definition ist XOR:  
\begin{tabular}{c|c|c}
$\oplus$ & 0 & 1 \\
\hline
0 & 0 & 1  \\
\hline                                   
1 & 1& 0 \\
\end{tabular}
\item[$\Rightarrow$] $\overline{DES(m,k)}=DES(\overline{m},\overline{k})$
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (iv) - \buchmann{6.5.5}}

\textbf{Teil 1:}\\
\begin{itemize}
\item $C_{16} = C_0$ (per Definition). 
\item Linksshift$_1(C_0)=C_1$
\item[$\Rightarrow$] Rechtsshift$_1(C_1)=C_0$
\item[$\Rightarrow$] Analog auch für $D_{16}$: Rechtsshift$_1(D_1)=D_0$
\vspace*{10mm}
\item[Cave] Nicht zu verwechseln mit dem $C_{j}$ aus den S-Boxen mit 1$ \le  j \le  8$ und 
$C_{i} = C_{i,1}C_{i,2}C_{i,3}C_{i,4}C_{i,5}C_{i,6}C_{i,7}C_{i,8}$  
\end{itemize}
\vspace*{10mm}
\textbf{Teil 2 (sehr gute Lösung im Buch!):}\\
\begin{itemize}
\item Sei $K_i$ der $i$-te Rundenschlüssel (mit den Bits 0 bis 47) und $C_i$ bzw. $D_i$ der Länge 28 für $1 \le i \le 16$.  
\item In PC2 erfolgt keine Permutation auf das 9,18,22 und 25 Bit.
\item Es gilt $K_i=\operatorname{PC2}(C_i,D_i)$
\item mit $K_1 = K_{16}$ und $C_{1,j} = C_{16,j+1}$ mit $0 \le j \le 26$ folgt:\\
$C_{1,i}=C_{1,i+1}$ für alle $i+1 \in \{9,18,22,25\}$ und \\
$C_{16,i}=C_{1,i+1}$ für alle $i \in \{9,18,22,25\}$\\
$\Rightarrow$ $C_{1,0} \cdots C_{1,8}, C_{1,9} \cdots C_{1,17}, C_{1,18} \cdots C_{1,21} ,C_{1.22} \cdots C_{1,24}$
und 
$C_{1,25} \cdots C_{1,27}$
sind jeweils gleich.
\item Mit $K_1 =K_2$ und $C_{1,j} = C_{16,j+}$ folgt dann analog: 
$C_{1,8} =C_{1,9}, C_{1,17}=C_{1,18}, C_{1,21} =C_{1,22}$
und $C_{1,24} =C_{1,25}$
\item[$\Rightarrow$]  Da $K_1=K_2=\cdots=K_{16}$
ist unsere Behauptung bewiesen.
\end{itemize}
\vspace*{10mm}
\textbf{Teil 3:}\\
\begin{itemize}
\item  alle Bits $C_{1,1} \cdots C_{1,28}$ = 0
\item  alle Bits $D_{1,1} \cdots D_{1,28}$ = 0 
\item  alle Bits $C_{1,1} \cdots C_{1,28}$ = 1
\item  alle Bits $D_{1,1} \cdots D_{1,28}$ = 1 
\item In allen anderen Zuständen sind die Teilschlüssel nicht gleich.
\item [$\Rightarrow$] Es gibt genau 4 schwache Schlüssel
\end{itemize}
\vspace*{10mm}
\textbf{Teil 4:}\\
\begin{itemize}
\item $k$ = 0x 01 01 01 01 01 01 01 01\\ $\Rightarrow$ PC1($k$) = 00000000000000
\vspace*{5mm}
\item $k$ = 0x FE FE FE FE FE FE FE FE) \\ $\Rightarrow$ PC1($k$)  = FFFFFFFFFFFFFF
\vspace*{5mm}
\item $k$ = 0x 1F 1F 1F 1F 0E 0E 0E 0E) \\ $\Rightarrow$ PC1($k$)  = 0000000FFFFFFF
\vspace*{5mm}
\item $k$ = 0x E0 E0 E0 E0 F1 F1 F1 F1)\\ $\Rightarrow$ PC1($k$)  =FFFFFFFF0000000
\end{itemize}
 
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (v) - \buchmann{3.23.26}}

\textbf{Teil 1 - Frage 1 aus Fußnote:}\\
\begin{itemize} 
\item Jedes reduzible Polynom lässt sich darstellen als Produkt von Polynomen (:="Teil-Polynom") (kleineren Grades)
\item Entweder das Teil-Polynom ist reduzibel und lässt sich wieder als Produkt darstellen... \textit{(rekursiv)}
\item Oder das Teil-Polynom ist irreduzibel.
\item[$\Rightarrow$] Jedes reduzible Polynom lässt sich darstellen als Produkt von irreduziblen Polynomen
\vspace*{5mm}
\item[$\Rightarrow$] Es folgt auch der Umkehrschluss: Lässt sich ein Polynom nicht durch ein irreduziblen Polynomen (kleineren Grades) teilen, so ist es selbst irreduzibel.
\end{itemize}
\vspace*{10mm}
\textbf{Teil 2 - Frage 2 aus Fußnote:}\\
\begin{itemize} 
\item Vorgehen: 
\begin{itemize} 
\item Polynom $f$ vom Grad $n$
\item Division von $f$ durch alle irreduziblen Polynome $g$ von Grad $\le n/2$ ausprobieren
\item Wenn $g \nmid f$ für alle $g$ gilt, so ist $f$ irreduzibel
\end{itemize} 
\vspace*{5mm}
\item[$\Rightarrow$] Alle irreduziblen Polynome bis 4.Grad sind:
\begin{alignat*}{2}
\{&1,&&\text{Grad }0\\
&x, x+1,&&\text{Grad }1\\
&x^2+x+1,&&\text{Grad }2\\
&x^3+x+1, x^3+x^2+1,&&\text{Grad }3\\
&x^4+x+1, x^4+x^3+1, x^4+x^3+x^2+x+1\}&\qquad&\text{Grad }4
\end{alignat*}
\begin{itemize}
\vspace*{-6mm}
\item Hinweis: Das Nullpolynom ist nicht irreduzibel!
\end{itemize}
\end{itemize}
\vspace*{10mm}
\textbf{Teil 3 - eigentliche Aufgabe}\\
\begin{itemize} 
\item $f(x)=x^8+x^4+x^3+x+1 \text{ in }(\Z/2\Z)$
\vspace*{3mm}
\item Testen der irreduziblem Polynome von Grad 1 als Divisior:\\
entspricht Prüfen auf Nullstellen, $f(0) = f(1) \equiv 1 \mod 2$\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 1 teilbar.
\vspace*{3mm}
\item Testen des irreduziblen Polynoms von Grad 2 als Divisior:\\
{\tiny \polylongdiv{x^8+x^4+x^3+x+1}{x^2+x+1}}\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 2 teilbar!
\item Testen der irreduziblem Polynome von Grad 3 als Divisior:\\
{\tiny \polylongdiv{x^8+x^4+x^3+x+1}{x^3+x+1}}\\
... weitere ...\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 3 teilbar!
\item Testen der irreduziblem Polynome von Grad 4 als Divisior:\\
{\tiny \polylongdiv{x^8+x^4+x^3+x+1}{x^4+x^3+1}}\\
... weitere ...\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 3 teilbar!
\vspace*{5mm}
\item[$\Rightarrow$] Polynom irreduzibel!
\end{itemize}


%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (vi) - One Time Pad}

Die sog. Verbesserung taugt nichts, da dadurch die perfekte Sicherheit verloren geht.\\
\vspace*{10mm}

\emph{Beweis und weitere Erläuterung sind auf einem ergänzenden Blatt von Herrn Straub zu finden. Dieses ist nachfolgend eingefügt.}

\includepdf{ex2/pdfs/otp.pdf}


%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (vii) - Feistel Chiffre}

Feistel Chiffre mit $f(x)=0:\qquad(L_{i},\enspace R_{i}) = (R_{i-1},\enspace L_{i-1} \xor 0) =  (R_{i-1},\enspace L_{i-1} )$
\newline
Damit ergibt sich für
\begin{itemize}
\item $r \mod 2 = 1:\qquad (L_{r},\enspace R_{r}) = (R_{0},\enspace L_{0})$
\item $r \mod 2 = 0:\qquad (L_{r},\enspace R_{r}) = (L_{0},\enspace R_{0})$
\end{itemize}
\vspace{5mm}
Feistel Chiffre mit
\newline
$f(x)=x:\qquad(L_{i},\enspace R_{i}) = (R_{i-1},\enspace L_{i-1} \xor R_{i-1})$
\newline
Damit ergibt sich für
\begin{itemize}
\item $r \mod 3 = 1:\qquad (L_{r},\enspace R_{r}) = (R_{0},\enspace L_{0} \xor R_{0})$
\item $r \mod 3 = 2:\qquad (L_{r},\enspace R_{r}) = (L_{0} \xor R_{0},\enspace L_{0})$
\item $r \mod 3 = 0:\qquad (L_{r},\enspace R_{r}) = (L_{0},\enspace R_{0})$
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (viii) - Strukturgleichheit?}

\begin{itemize}
\item $\gf(2^{2})$ mit dem Vertretersystem $\{0, 1, X, X+1\}$
\begin{itemize}
\item ist ein endlicher Körper
\item alle Elemente außer $0$ invertierbar bzgl. Multiplikation
\end{itemize}
\vspace*{5mm}
\item $\Z/4\Z=\{4\Z, 1 + 4\Z, 2+4\Z, 3+4\Z\}$\\
\begin{itemize}
\item ist kein Körper
\item $0$ und $2$ nicht invertierbar bzgl. Multiplikation 
\item $2+4\Z$ nicht invertierbar bzgl. Multiplikation wegen $\gcd(2,4)=2\neq1$\\  
\end{itemize}
\vspace*{5mm}
\item[$\Rightarrow$]$\gf(2^{2})$ nicht isomorph zu $\Z/4\Z$\\
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection*{Übung (ix) - Kongruenz von Polynomen}

\begin{itemize}
\item Umwandeln in Bit-Schreibweise
\begin{alignat*}{10}
g(x)&=&&1x^7&+&1x^6&+&0x^5&+&0x^4&+&1x^3&+&1x^2&+&0x^1&+&0x^0\\
b_{bin}&=&&1&&1&&0&&0&&1&&1&&0&&0&\\
b_{hex}&=&&C&&&&&&&&C&&&&&&&\\
\end{alignat*}
\item  Inverses aus Tabelle ablesen (da AES)
\begin{alignat*}{10}
b^{-1}_{hex}&=&&1&&&&&&&&B&&&&&&&\\
b^{-1}_{bin}&=&&0&&0&&0&&1&&1&&0&&1&&1&\\
g^{-1}(x)&=&&0x^7&+&0x^6&+&0x^5&+&1x^4&+&1x^3&+&0x^2&+&1x^1&+&1x^0\\
\end{alignat*}
\item Umformen der Gleichung
\begin{alignat*}{2}
g(x)*f(x)&\equiv (x^4+x+1) &&\mod m(x)\\
g(x)*g^{-1}(x)*f(x)&\equiv g^{-1}(x)*(x^4+x+1) &&\mod m(x)\\
f(x)&\equiv (x^8+x^7+x^4+x^3+x^2+1) &&\mod m(x)\\
\end{alignat*}
\item Polynomdivision
{\scriptsize
\polylongdiv{x^8+x^7+x^4+x^3+x^2+1}{x^8+x^4+x^3+x+1}\\
}
\vspace*{5mm}
\item[$\Rightarrow$] Ergebnis\\
\begin{displaymath}
f(x)=x^7+x^2+x 
\end{displaymath}
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (x) - Inverses Polynom?}

\textbf{Teil 1 - Schlechtes Beispiel für erw. Euklid:}\\
\begin{itemize}
\item für $f(x)=x$, $m(x)=x^4+x+1$
\item Polynomdivision\\
\polylongdiv{x^4+x+1}{x}
\item $q(x)=x^3+1$, $r = 1$
\vspace*{5mm}
\item[$\Rightarrow$] Ergebnis: $f^{-1}(x)=x^3+1$
\end{itemize}
\vspace*{10mm}
\textbf{Teil 2 - Besseres Beispiel für erw. Euklid:}\\
\begin{itemize}
\item für $g(x)=x^3+x$, $m(x)=x^4+x+1$
\vspace*{5mm}
\item Polynomdivision 1\\
\polylongdiv{x^4+x+1}{x^3+x}\\
$\Rightarrow q_1(x)=x,\qquad r_1(x) = x^2+x+1$
\item Da der Rest der vorigen Polydiv ungleich 1\\
$\Rightarrow$ Polydiv mit Divisor durch Rest
\vspace*{2mm}
\item Polynomdivision 2\\
\polylongdiv{x^3+x}{x^2+x+1}\\
$\Rightarrow q_2(x)=x+1,\qquad r_2(x) = x+1$
\item Da der Rest der vorigen Polydiv ungleich 1\\
$\Rightarrow$ Polydiv mit Divisor durch Rest
\vspace*{2mm}
\item Polynomdivision 2\\
\polylongdiv{x^2+x+1}{x+1}\\
$\Rightarrow q_3(x)=x,\qquad r_3(x) = 1$
\item Rest der vorigen Polydiv gleich 1\\
$\Rightarrow$ fertig!
\vspace*{2mm}
\item Tabelle für erweiterten Euklid\\
\footnotesize
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\rowcolor{grau} $k$ & 0 & 1 & 2 & 3 & 4 \\
\hline
$r_k$ & $x^4+x+1$ & $x^3+x$ & $r_2(x)=x^2+x+1$ & $r_2(x)=x+1$ & $r_3(x)=1$\\
\hline
$q_k$ & --- & $q_1(x)=x$ & $q_2(x)=x+1$ & $q_3(x)=x$ & $x+1$ \\
\hline
$x_k$ & 1 & 0 & 1 & $x$ & $x^2+1$\\
\hline
$y_k$ & 0 & 1 & $x$ & $x^2+x+1$ & \cellcolor{rot}$x^3+x^2$\\
\hline
\end{tabular}
\normalsize
\vspace*{5mm}
\item[$\Rightarrow$] Ergebnis: $f^{-1}(x)=x^3+x^2$
\end{itemize}
